package algorithm_demo.leetcode;

/**
 * 704. 二分查找
 * <a href="https://leetcode.cn/problems/binary-search/">https://leetcode.cn/problems/binary-search/</a>
 *
 * @author Api
 * @date 2023/5/7 13:06
 */
public class Problem_704_BinarySearch {
    //查找下标
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0;//思考左右边界，这是前提，一定不能漏掉，目标数值
        int right = len-1;
        while(left < right){//不加思考地写下while(left<right),退出循环时也不必思考返回left还是right
            //1. 先取左中位数，以后根据分支的逻辑，决定是否要修改成右中位数；
            //2. 注意：取中位数最好的写法是左边界+右边界，再无符号右移
            //在括号内添加+1，表示将中位数修改成右中位数
            int mid = (left+right+1)>>>1;
            //先写容易想的分支逻辑，通常这个逻辑是排除中位数，但并不绝对
            if(nums[mid] > target){
                right = mid-1;
            }else{
                //在上一步分支编写正确的前提下，另一个分支的代码几乎是固定的，而不必过多思考逻辑上的正确性，注意：在循环中无需单独对中位数做判断
                left = mid;
            }
        }
        //注意：写完分支逻辑之后，再看看是否有必要调整中位数。
        //这里取左中位数，但分支逻辑可能在左中位数的地方不收缩，从而进入死循环，因此需要把中位数调整成右中位数

        //退出循环以后，考虑是否需要后处理。即检查通过“排除”和“夹逼”以后，最后剩下的那个数是否符合题意。
        if(nums[left] == target){
            return left;
        }
        return -1;
    }


    //判断是否存在
    public boolean exist(int[] sortedArr, int num){
        if (sortedArr == null || sortedArr.length == 0){
            return false;
        }
        int left = 0;
        int right = sortedArr.length-1;
        int mid = 0;
        while(left < right){
            mid = left + ((right - left)>>1);
            if (sortedArr[mid] == num){
                return true;
            }else if(sortedArr[mid] > num){
                right = mid-1;
            }else{
                left = mid + 1;
            }
        }
        return sortedArr[left] == num;
    }
}
